package gps;

import gps.api.GPSProblem;
import gps.api.GPSRule;
import gps.api.GPSState;
import gps.exception.NotAppliableException;
import gps.gui.Frame;
import gps.implementationAPI.GPSStateImplementation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import javax.swing.JFrame;

import org.apache.log4j.Logger;

public class GPSEngine {

	private static final Logger LOGGER = Logger.getLogger(GPSEngine.class);

	static private List<GPSNode> open = new ArrayList<GPSNode>();
	//static private List<GPSNode> closed = new LinkedList<GPSNode>();
	
	static private GPSProblem problem;
	static private SearchStrategy strategy;

	private static Map<GPSState, List<GPSNode>> openHash = new HashMap<GPSState, List<GPSNode>>();
	private static Map<GPSState, List<GPSNode>> closeHash = new HashMap<GPSState, List<GPSNode>>();

	
	private static GPSNode solution;
	
	public static void engine(GPSProblem myProblem, SearchStrategy myStrategy) {

		Long initialTime = System.currentTimeMillis();
		
		
		problem = myProblem;
		strategy = myStrategy;
		long processed = 0;

		
		
		GPSNode rootNode = new GPSNode(problem.getInitState(), 0);
		boolean finished = false;
		boolean failed = false;
		long explosionCounter = 0;

		open.add(rootNode);
		
		//--
		List<GPSNode> ol = new LinkedList<GPSNode>();
		openHash.put(rootNode.getState(), ol);
		ol.add(rootNode);
		//--
		while (!failed && !finished) {
			//LOGGER.info("Cantidad en Open: " + open.size());
			//LOGGER.info("Cantidad en process: " + procesados);
			processed++;
			if (open.size() <= 0) {
				failed = true;
			} else {
				GPSNode currentNode = open.get(0);
			//	closed.add(currentNode);
				//--
				
				List<GPSNode> closeList = closeHash.get(currentNode.getState());
				if(closeList == null){
					closeList = new LinkedList<GPSNode>();
					closeHash.put(currentNode.getState(), closeList);
				}
				closeList.add(currentNode);
				openHash.get(currentNode.getState()).remove(currentNode);
				//--
				open.remove(0);

				if(processed % 5000 == 0){
					System.out.println(open.size() + "\t\t" + (processed) + "\t\t" + currentNode.getCost());
				}
				
				if (isGoal(currentNode)) {
					finished = true;
					//System.out.println(currentNode.getSolution());
					//printSolution(currentNode);
					solution = currentNode;
					System.out.println("Expanded nodes: " + explosionCounter);
					System.out.println("Nodos abiertos: " + open.size());
					System.out.println("Nodos cerrados:" + processed);
				} else {
					explosionCounter++;
					explode(currentNode);
				}
			}
		}
		System.out.println("Total time: " + ((System.currentTimeMillis() - initialTime)/1000) + " seconds");
		
		if (finished) {
			System.out.println("OK! solution found!");
			showSolution(solution);
		} else if (failed) {
			System.err.println("FAILED! solution not found!");
		}
	}

	private static void printSolution(GPSNode currentNode) {
		GPSNode n = currentNode;
		
		LinkedList<String> movements = new LinkedList<String>();
		while(n != null){
			movements.addFirst(n.getState().toString() + " " + n.getCost());
			n = n.getParent();
		}
		
		for(String s: movements){
			System.out.println(s);
		}
		
	}
	private static boolean isGoal(GPSNode currentNode) {
		return currentNode.getState() != null && problem.getGoalState().compare(currentNode.getState());
	}
	
	private static boolean explode(GPSNode node) {
		List<GPSNode> newNodes = new ArrayList<GPSNode>();
		if(problem.getRules() == null){
			System.err.println("No rules!");
			return false;
		}
		for (GPSRule rule : problem.getRules()) {
			GPSState newState = null;
			try {
				newState = rule.evalRule(node.getState());
			} catch (NotAppliableException e) {
				// Do nothing
			}
			
			if (newState != null
					//&& !checkBranch(node, newState)
					&& !checkOpenAndClosedHash(node.getCost() + rule.getCost(),
							newState)) {
				GPSNode newNode = new GPSNode(newState, node.getCost()
						+ rule.getCost());
				newNode.setParent(node);
				newNodes.add(newNode);
			}
		}
		newNodes = listWithOutSimetrics(newNodes);
		if (strategy == SearchStrategy.GS) {
			newNodes = orderForGS(newNodes);
			for (int i = newNodes.size()-1; i >= 0; i--) {
				addNode(newNodes.get(i));
			}
		} else {
			for (GPSNode n: newNodes) {
				addNode(n);
			}
		}
		return true;
	}
	
	private static List<GPSNode> listWithOutSimetrics (List<GPSNode> list) {
		List<GPSNode> newList = new LinkedList<GPSNode>();
		boolean flag = false;
		if (!list.isEmpty()) {
			for (int i = 0; i < list.size(); i++) {
				for (int j = 0; j < i; j++) {
					if (list.get(i).getState().simetric(list.get(j).getState())) {
						flag = true;
					}
				}
				if (!flag) {
					newList.add(list.get(i));
				}
				flag = false;
			}
		}
		return newList;
	}
	
	private static List<GPSNode> orderForGS (List<GPSNode> list) {
		Collections.sort(list, new Comparator<GPSNode>() {
					public int compare(GPSNode o1, GPSNode o2) {
						Integer h1 = problem.getHValue(o1.getState());
						Integer h2 = problem.getHValue(o2.getState());
						if (h1 < h2) {
							return -1;
						} else if (h1 == h2) {
							return 0;
						} else {
							return 1;
						}
					}
				});
		return list;
	}

	private static void addNode(GPSNode node) {
		switch (strategy) {
		case BFS:
			open.add(node);
			break;
		case DFS: case GS:
			((ArrayList<GPSNode>) open).add(0,node);
			break;
		case AStar:
			int index = Collections.binarySearch(open, node,
					new Comparator<GPSNode>() {

						public int compare(GPSNode o1, GPSNode o2) {
							Integer f1 = o1.getCost()
									+ problem.getHValue(o1.getState());
							Integer f2 = o2.getCost()
									+ problem.getHValue(o2.getState());
							if (f1 < f2) {
								return -1;
							} else if (f1 == f2) {
								return 0;
							} else {
								return 1;
							}
						}
					});
			if (index >= 0) {
				((ArrayList<GPSNode>) open).add(index, node);
			} else {
				((ArrayList<GPSNode>) open).add(-1 * (index + 1), node);
			}
			break;
		default:
			open.add(node);
			break;
		}
		
		List<GPSNode> openList = openHash.get(node.getState());
		if(openList == null){
			openList = new LinkedList<GPSNode>();
			openHash.put(node.getState(), openList);
		}
		openList.add(node);
		
	}

	private static boolean checkOpenAndClosedHash(Integer cost, GPSState state){

		
		
		List<GPSNode> openNodes = getStateFromHash(openHash, state);
		if(openNodes != null){
			for(GPSNode n: openNodes){
				if(n != null && n.getCost() < cost)
					return true;
			}
		}
		
		List<GPSNode> closeNodes = getStateFromHash(closeHash, state);
		if(closeNodes != null){
			for(GPSNode n: closeNodes){
				if(n != null && n.getCost() < cost)
					return true;
			}
		}
		
		return false;
	}
	
	private static List<GPSNode> getStateFromHash(Map<GPSState, List<GPSNode>> hash,GPSState state){
	
		GPSState auxState = state;
		List<GPSNode> ret = null;
		for(int i = 0 ; i < 4 ; i++){
			ret = hash.get(auxState);
			if(ret != null){
				break;
			}
			auxState = GPSStateImplementation.rotate90((GPSStateImplementation)auxState);
		}
		
		if(ret == null){
			ret = hash.get(GPSStateImplementation.getAsMirror(Direction.HORIZONTAL, (GPSStateImplementation) state));
		}
		
		if(ret == null){
			ret = hash.get(GPSStateImplementation.getAsMirror(Direction.VERTICAL, (GPSStateImplementation) state));
		}
		
		return ret;
	}
	
//	private static boolean checkOpenAndClosed(Integer cost, GPSState state) {
//		for (GPSNode openNode : open) {
//			if (openNode.getState().equals(state) && openNode.getCost() < cost) {
//				return true;
//			}
//		}
//		for (GPSNode closedNode : closed) {
//			if (closedNode.getState().equals(state)
//					&& closedNode.getCost() < cost) {
//				return true;
//			}
//		}
//		return false;
//	}

	private static boolean checkBranch(GPSNode parent, GPSState state) {
		if (parent == null) {
			return false;
		}
		return checkBranch(parent.getParent(), state)
				|| state.equals(parent.getState());
	}
	
	
	private static void showSolution(GPSNode currentNode) {
	
		GPSNode n = currentNode;
		
		LinkedList<GPSState> states = new LinkedList<GPSState>();
		System.out.println("Costo: " + currentNode.getCost());
		
		while (n != null){
			states.addFirst(n.getState());
			n = n.getParent();
		}
		
		
		Frame f = new Frame();
		f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		f.setSize(800, 800);
		f.setVisible(true);
		
		for(GPSState state: states){
		try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			f.setState((GPSStateImplementation) state);
		}
	
		System.out.println("Listooo");
	}

}
